package com.atcumt.Write.writeStructures;

import java.util.HashMap;
import java.util.Map;

/* 
 * HashMap + 双向链表
 * save(key, value)，首先在 HashMap 找到 Key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。
 * 如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过 popTail 淘汰掉队尾的节点，同时在 HashMap 中移除 Key。
 * get(key)，通过 HashMap 找到 LRU 链表节点，把节点插入到队头，返回缓存的值。
 */
class DLinkedNode {
    String key;
    int value;
    DLinkedNode pre;
    DLinkedNode next;
}

public class WriteLRUCache {

    private Map<String, DLinkedNode> cache = new HashMap<>();
    private int count;
    private int capacity;
    private DLinkedNode head, tail;

    public WriteLRUCache(int capacity) {
        this.count = 0;
        this.capacity = capacity;

        head = new DLinkedNode();
        head.pre = null;

        tail = new DLinkedNode();
        tail.next = null;

        head.next = tail;
        tail.pre = head;
    }

    public int get(String key) {

        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1; // should raise exception here.
        }

        // move the accessed node to the head;
        this.moveToHead(node);

        return node.value;
    }

    public void put(String key, int value) {
        DLinkedNode node = cache.get(key);

        if (node == null) {

            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;

            this.cache.put(key, newNode);
            this.addNode(newNode);

            ++count;

            if (count > capacity) {
                // pop the tail
                DLinkedNode tail = this.popTail();
                this.cache.remove(tail.key);
                --count;
            }
        } else {
            // update the value.
            node.value = value;
            this.moveToHead(node);
        }
    }

    /**
     * Always add the new node right after head;
     */
    private void addNode(DLinkedNode node) {
        node.pre = head;
        node.next = head.next;

        head.next.pre = node;
        head.next = node;
    }

    /**
     * Remove an existing node from the linked list.
     */
    private void removeNode(DLinkedNode node) {
        DLinkedNode pre = node.pre;
        DLinkedNode post = node.next;

        pre.next = post;
        post.pre = pre;
    }

    /**
     * Move certain node in between to the head.
     */
    private void moveToHead(DLinkedNode node) {
        this.removeNode(node);
        this.addNode(node);
    }

    // pop the current tail.
    private DLinkedNode popTail() {
        DLinkedNode res = tail.pre;
        this.removeNode(res);
        return res;
    }

    /* 
     * 测试
     */
    public static void main(String[] args) {
        WriteLRUCache lRUCache = new WriteLRUCache(2);
        lRUCache.put("1", 1); // 缓存是 {1=1}
        lRUCache.put("2", 2); // 缓存是 {1=1, 2=2}
        System.out.println(lRUCache.get("1")); // 1
        lRUCache.put("3", 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        System.out.println(lRUCache.get("2")); // -1 (未找到)
        lRUCache.put("4", 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        System.out.println(lRUCache.get("1")); // -1 (未找到)
        System.out.println(lRUCache.get("3")); // 3
        System.out.println(lRUCache.get("4")); // 4
    }
}